Skip to main content

Permutation Problem

The permutation problem involves finding all possible arrangements of elements from a given set using a backtracking algorithm. This problem can be approached considering either arrays without duplicate elements or arrays that include duplicates.

Permutations without Equal Elements​

Description​

Given an integer array without duplicate elements, the task is to return all possible permutations.

Backtracking Process​

The permutation generation is visualized as a series of choices:

  1. Choices and State: The choices array contains all elements of the input array, and the state array contains elements selected so far.
  2. Recursive Tree Representation: Starting with an empty state, each recursive call represents a choice made, progressing until all elements are chosen.

Pruning Repeated Choices​

  • Boolean Array (selected): Utilized to track if an element from choices has been selected.
  • Pruning: Skip over already selected elements to reduce redundancy and exploration space.

Example: Recursive Tree and Pruning​

  • Initial Choices: [1, 2, 3]
  • Process: Select 1, then 2, then 3 to form a permutation [1, 2, 3].
  • Backtracking: Reverse selections step-by-step to explore other permutations.
def backtrack(state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]):
    if len(state) == len(choices):
        res.append(list(state))
        return
    for i, choice in enumerate(choices):
        if not selected[i]:
            selected[i] = True
            state.append(choice)
            backtrack(state, choices, selected, res)
            selected[i] = False
            state.pop()

def permutations_i(nums: list[int]) -> list[list[int]]:
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

Permutations with Equal Elements​

Description​

Generate unique permutations from an array that may contain duplicates.

Handling Duplicates​

  • Marking: Differentiate identical elements by marking them differently.
  • Hash Set (duplicated): Used to track elements tried in the current recursive call to prevent generating duplicate permutations.

Example: Eliminating Duplicates​

  • Input: [1, 1, 2]
  • Process: Choose first 1, then 2, marking the next identical 1 differently to prevent duplicate permutations.
def backtrack(state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]):
    duplicated = set[int]()
    if len(state) == len(choices):
        res.append(list(state))
        return
    for i, choice in enumerate(choices):
        if not selected[i] and choice not in duplicated:
            duplicated.add(choice)
            selected[i] = True
            state.append(choice)
            backtrack(state, choices, selected, res)
            selected[i] = False
            state.pop()

def permutations_ii(nums: list[int]) -> list[list[int]]:
    res = []
    backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
    return res

Comparison of Pruning Methods​

  • Repeated Choice Pruning: Prevents an element from appearing more than once in a permutation using a single selected array throughout the search.
  • Equal Element Pruning: Ensures that duplicate elements are selected only once per recursive call level using a duplicated set in each recursion.